![]() |
The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson Wiley Computer Publishing, John Wiley & Sons, Inc. ISBN: 0471353817 Pub Date: 03/01/99 |
Previous | Table of Contents | Next |
A good key schedule should have the property that, when an attacker guesses some subset of the key bits, he does not learn very much about the subkey sequence or other internal operations in the cipher. The Twofish key schedule has this property.
Consider an attacker who guesses the even words of the key Me. He learns nothing of the key S to g. For each round subkey block, he now knows Ai. If he guesses K0, he can compute the corresponding K1. He can carry this attack out against as many round subkeys as he likes, but each guess takes 32 bits. We can see no way for the attacker to actually test the 96-bit guess that it would take to attack even one rounds subkey in this way on the full Twofish.
An alternative is to guess the key input S to g. This is only half the length of the full key M, but provides no information about the round keys Ki. The differential attack described in Section 9.2 is the best way we were able to find to test such a partial key guess. We can see no way to test a guess of S on the full 16-round Twofish.
Related-key cryptanalysis [Bih94, KSW96, KSW97] uses a ciphers key schedule to break plaintexts encrypted with related keys. In its most advanced form, differential related-key cryptanalysis, both plaintexts and keys with chosen differentials are used to recover the keys. This type of analysis has had considerable success against ciphers with simplistic key schedulese.g., GOST [GOST89] and 3-Way [DGV94b, Dae95]and is a realistic attack in some circumstances. A conventional attack is usually judged in terms of the number of plaintexts or ciphertexts needed for the attack, and the level of access to the cipher needed to get those texts (i.e., known plaintext, chosen plaintext, adaptive chosen plaintext). A related-key attack adds another parameternumber of related keys under which the plaintexts will be encrypted.
A slide attack occurs in an iterated cipher when the encryption of one block for rounds 1 through n is the same as the encryption of another block for rounds s + 1 to s + n. An attacker can look at two encryptions, and can slide the rounds forward in one of them relative to another. S-1 [Anon95] can be broken with a slide attack [Wag95a]. Travois [Yuv97] has identical round functions, and can also be broken with a slide attack. Conventional slide attacks allow one to break the cipher with only known- or chosen-plaintext queries; however, as we shall see next, there is a generalization to related-key attacks as well.
Related-key slide attacks were first discovered by Biham in his attack on a DES variant [Bih94]. To mount a related-key slide attack on Twofish, an attacker must find a pair of keys M, M* such that the key-dependent S-boxes in g are unchanged, but the subkey sequences slide down one round. This amounts to finding, for each of the eight byte-permutations used for subkey generation, a change in the keys such that:
si(j, M) = si(j + 2s, M*)
for n values of j. In total, this requires 8n of these relations to hold.
Let us look in more detail for a fixed key M. Let m ≥ {5,...,8} be the number of S-boxes used to compute the round keys that are affected by the difference between M and M*. Observe that m ≥ 5 due to the restriction that S cannot change and the properties of the RS matrix that at least five inputs must change to keep the output constant. There are at most (8 m)232m-128 possible choices of M*. We have a total of nm 8-bit relations that need to be satisfied. The expected number of M* that satisfy these relations is thus (8 m).2-8nm+32m-128. For n ≥ 4 this is dominated by the case m = 5; we will ignore the other cases for now. So for each M we can expect about 238-40n keys M* that support a slide attack for n ≥ 4. This means that any specific key is unlikely to support a slide attack with n ≥ 4. Over all possible key pairs, we expect 2293-40n pairs M, M* for which a slide of n ≥ 4 occurs. Thus, it is unlikely that a pair exists at all with n ≥ 8.
Swapping Key Halves. It is worth considering what happens when we swap key halves. That is, we swap the key bytes so that the values of Me and Mo are exchanged. In that case, the sequence of Ai and Bi values totally changes because of the different index values used. We can see no useful attack that could come from this.
Permuting the Subkeys. Although there is no known attack stemming from it, it is interesting to ask whether there exist pairs of keys that give permutations of one anothers subkeys. There are 20! ways that the rounds subkey blocks could be permuted. This is almost as large as 264, and so there may very well be pairs of keys that give permutations of one anothers round subkey blocks.
A related-key differential attack seeks to mount a differential attack on a block cipher through the key, as well as or instead of through the plain-text/ciphertext port. Against Twofish, such an attack must control the sub-key difference sequence for at least the rounds in the middle. For the sake of simplifying discussions of the attack, let us consider an attacker who wants to put a chosen subkey difference into the middle 12 rounds subkeys. That is, he wants to change M to M* and control D[i, M, M*] for i = 12,...,35. At the same time, he needs to keep the g function, and thus the key S, from changing. All else being equal, the longer the key, the more freedom an attacker has to mount a related-key differential attack. We thus will assume the use of 256-bit keys for the remainder of this section. Note that a successful related-key attack on 128- or 192-bit keys that gets only zero subkey differences in the rounds whose subkey differences it must control translates directly to an equivalent related-key attack on 256-bit keys.
Consider the position of the attacker if he attempts a related-key differential attack with different S keys. This must result in different g outputs for all inputs, since we know that there are no pairs of S values that lead to identical S-boxes. Assuming the pair of S values does not lead to linearly related S-boxes, it will not be possible to compensate for this change in S with changes in the subkeys in single rounds. If we assume 12 active rounds in the attack, the added difficulty is approximately that of adding 24 active S-boxes to the existing related-key attack. For this reason, we believe that any useful related-key attack will require a pair of keys that keeps S unchanged.
The simplest related-key attack to analyze is the one that keeps both S and also the middle 12 rounds subkeys unchanged. It thus seeks to generate identical A and B sequences for 12 rounds, and thus to keep the individual byte sequences used to derive A and B identical.
The RS code used to derive S from M strictly limits the ways an attacker can change M without altering S. The attacker must try to keep the number of active subkey generating S-boxes as low as possible, since each active S-box is another constraint on his attack. The attacker can keep the number of active S-boxes down to five without altering S, so this is what he should do. With only the key bytes affecting these five subkey generation S-boxes active, he can alter between one and four bytes in all five S-boxes; the nature of the RS matrix is that if he needs to alter four bytes in any one of these S-boxes, he must alter bytes in all five. In practice, in order to maximize his control over the byte sequences generated by these S-boxes, he must alter four bytes in all five active S-boxes.
To get zero subkey differences, the attacker must get zero differences in the byte sequences generated by all five active S-boxes. Consider a single such byte sequence: the attacker tries to find a pair of four-byte key inputs such that they lead to identical byte sequences in the middle 12 rounds, which means the middle 12 bytes. There are 263 pairs of key inputs from which to choose, and about 295 possible byte sequences available. If the byte sequences behave more-or-less like random functions of the key inputs, this implies that it is extremely unlikely that an attacker can find a pair of key inputs that will get identical byte sequences in these middle 12 rounds. We discuss this kind of analysis of byte sequences in Section 8.2.3. From this analysis, we would not expect to see a pair of keys for even one S-box with more than eight successive bytes unchanged, and we would expect even eight successive bytes of unchanged byte sequence to require control of all four key bytes into the S-box. We would expect a specific pair of key bytes to be required to generate these similar byte sequences.
To extend this to five active S-boxes, we expect there to be, at best, a single pair of values for the 20 active key bytes that leave the middle eight subkeys unchanged.
Previous | Table of Contents | Next |